package recursive;

import java.util.ArrayList;
import java.util.List;

/**
 * 组合问题
 * https://leetcode-cn.com/problems/combinations/
 * 给定两个数 n 和 k，返回从 1 到 n 数组中所有 k 个数的情况
 * 解题思路：针对数组中的每一个数，同样是有两种情况，选择或者不选择
 * 注意：1、确定递归边界——区间左闭右闭，左边从1开始，计数器大于右边界才可以包含住左右边界
 *      2、最终共享变量中数据的数量要等于 k 才可以（大于 k 个的可以直接丢弃）
 *      3、保护与还原现场——加进共享变量中的数据，在使用完后要记得删除
 *      4、List 中的 add 方法是浅复制，要使用深复制才不会修改已经进入结果集的结果
 *      5、List 中的 remove 方法入参是下标，注意 i 不是共享变量实际的长度
 *      6、如果不想每次递归都传递 n 和 k，可以定义为类变量
 * 测试案例：{4,2}——[3.4],[2,4],[2,3],[1,4],[1,3],[1,2]
 */
public class Combinations {
    private List<List<Integer>> result = new ArrayList<>();
    private List<Integer> res = new ArrayList<>();
    private int count = 0;
    private int end = 0;
    public List<List<Integer>> combine(int n, int k) {
        end = n;
        count = k;
        perform(1);
        return result;
    }

    private void perform(int i){
        if (i > end){
            if (res.size() == count) { // 只取最终结果数量等于k的情况
                List<Integer> r = new ArrayList<>(); // 深复制结果
                r.addAll(res);
                result.add(r);
            }
            return;
        } else if (res.size() > count){ // 如果长度已经大于所需长度了，则该支没有继续递归下去的必要
            return;
        }

        perform(i + 1); // 不加入子集，继续递归
        res.add(i); // 加入子集
        perform(i + 1);
        res.remove(res.size()-1); // 还原到上一步状态
    }
}
